package binaryTree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

/**实现二叉树的层次遍历
 * 
 * */
public class LevelOrder<AnyType> {
	
	/**
	 * 层序遍历树 用到了先进先出的队列
	 */
	public void levelOrder(BTNode<AnyType> root) {
		if (root == null)
			return;
		//初始化一个队列
		Queue queue = new ArrayDeque<BTNode>();
		//把根节点加入到队列中,因为Queue继承了Collection方法
		queue.add(root);
		//当该队列不为空时
		while (!queue.isEmpty()) {
			
			BTNode<AnyType> temp = (BTNode) queue.poll();
			System.out.print(temp.getData()+"  ");
			//按照层次加入到队列中
			
			if (temp.getLeftChild() != null) {
				
				queue.add(temp.getLeftChild());
				
			}
			if (temp.getRightChild()!= null){
				queue.add(temp.getRightChild());
				
			}
			
		}
	}
	
	//测试函数
	public static void main(String[] args){
		BinaryTree bt1=new BinaryTree();
		Scanner in=new Scanner(System.in);
		System.out.println("请输入字符串，以先序的顺序创建创建二叉树：");
		//供测试数字串 ：abd   ce  f  
		String str=in.nextLine();
		/**将字符串转换成字符数组*/
		char[] tree=str.toCharArray();
		/**创建包装类的数组*/
		Character[] preOrder = new Character[tree.length];
		/**遍历数组，景数组中非空格的字符包装后，存入包装类数组，对空格字符赋值为null*/
		for(int i=0;i<tree.length;i++){
			if(tree[i]==' '){
				preOrder[i]=null;
			}else{
//				preOrder[i]=new Character(tree[i]);
				preOrder[i]=tree[i];
			}
		}
		/**创建二叉树*/
		bt1.setNode(((BinaryTree) bt1).createBTByPreOrder(preOrder));
		
		//层次遍历
		System.out.println("层次遍历的结果为：");
		new LevelOrder().levelOrder(bt1.getNode());
		
	}
}
